function [parent, attrib, split, prob] = id3_train(data, dataID, useAttrib, root, label_count)
    if (size(find(data(:, 1) == data(1,1)), 1) == size(data, 1)) 
%        disp(size(data));
        attrib = -1;
        split = 0;
        parent = [];
        prob = zeros(1, label_count);
        prob(1, data(1,1)) = 1;
    else
        [N, K] = size(data);
        K = (K-1)/2;
        min_entropy = 10000;
        attrib_index = 0;
        min_split_point = 0;
		for i = 1 : K
            if (useAttrib(i) > 0) 
                [split_point, entropy] = id3_find_split([data(:, i*2), data(:, i*2+1)], data(:, 1));
                if (entropy < min_entropy) 
                    attrib_index = i;
                    min_split_point = split_point;
                end
%                disp([entropy, i, split_point]);
            end                         
        end            
        parent = [];
        attrib = -1;
        split = 0;
        
        if (attrib_index == 0)

            prob = zeros(1, label_count);
            for i = 1 : label_count
                prob(1, i) = nnz(data(:, 1) == i) / N;
            end
            return;
        end
               
        smaller_index = find(data(:, attrib_index*2) < min_split_point);
        bigger_index = find(data(:, attrib_index*2+1) > min_split_point);
        
        
        useAttrib(attrib_index) = useAttrib(attrib_index) - 1;
        
        attrib = attrib_index;
        split = min_split_point;
        nodes_count = 1;
        prob = zeros(1, label_count);
        if (size(smaller_index, 1) >= 1) 
            [new_parent, new_attrib, new_split, new_prob] = id3_train(data(smaller_index, :), dataID(smaller_index), useAttrib, nodes_count+root, label_count);
            nodes_count = nodes_count + size(new_attrib, 2);
            attrib = [attrib, new_attrib];
            split = [split, new_split];
            parent = [parent, root, new_parent];
            prob = [prob; new_prob];
        end;
        if (size(bigger_index, 1) >= 1) 
            [new_parent, new_attrib, new_split, new_prob] = id3_train(data(bigger_index, :), dataID(bigger_index), useAttrib, nodes_count+root, label_count);
            nodes_count = nodes_count + size(new_attrib, 2);
            attrib = [attrib, new_attrib];
            split = [split, new_split];
            parent = [parent, root, new_parent];
            prob = [prob; new_prob];
        end;
    end
end

            


